package com.cat.dataStructure02;

class Checkout {
    static int N = ((int) (1e5 + 10));
    static int[] deque = new int[N], nums = new int[N];
    int h, t, n, size;
    public Checkout() {
    }

    public int get_max() {
        if (size > 0) {
            return nums[deque[h]];
        }
        return -1;
    }

    public void add(int value) {
        nums[n] = value;
        while (h < t && nums[deque[t - 1]] <= value) {
            t--;
        }
        deque[t++] = n++;
        size++;
    }

    public int remove() {
        if (size > 0) {
            if (n - size == deque[h]) { // 要弹出位置的下标
                h++;
            }
            return nums[n - size--];
        }
        return -1;
    }
}